{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Prime Pairs With Target Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #enumeration #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #枚举 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findPrimePairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #和等于目标值的质数对"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> 。如果两个整数 <code>x</code> 和 <code>y</code> 满足下述条件，则认为二者形成一个质数对：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= x &lt;= y &lt;= n</code></li>\n",
    "\t<li><code>x + y == n</code></li>\n",
    "\t<li><code>x</code> 和 <code>y</code> 都是质数</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你以二维有序列表的形式返回符合题目要求的所有 <code>[x<sub>i</sub>, y<sub>i</sub>]</code> ，列表需要按 <code>x<sub>i</sub></code> 的 <strong>非递减顺序</strong> 排序。如果不存在符合要求的质数对，则返回一个空数组。</p>\n",
    "\n",
    "<p><strong>注意：</strong>质数是大于 <code>1</code> 的自然数，并且只有两个因子，即它本身和 <code>1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 10\n",
    "<strong>输出：</strong>[[3,7],[5,5]]\n",
    "<strong>解释：</strong>在这个例子中，存在满足条件的两个质数对。 \n",
    "这两个质数对分别是 [3,7] 和 [5,5]，按照题面描述中的方式排序后返回。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>可以证明不存在和为 2 的质数对，所以返回一个空数组。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [prime-pairs-with-target-sum](https://leetcode.cn/problems/prime-pairs-with-target-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [prime-pairs-with-target-sum](https://leetcode.cn/problems/prime-pairs-with-target-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10', '2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        def isPrime(x):\n",
    "            if x < 2: return False\n",
    "            if x in (2, 3): return True\n",
    "            if x % 6 not in (1, 5): return False\n",
    "            return all(x % i and x % (i + 2) for i in range(5, int(x ** 0.5) + 1, 6))\n",
    "        if n < 5 or n & 1: return [[2, n - 2]] if isPrime(n - 2) else []\n",
    "        return [[i, n - i] for i in range(3, n + 2 >> 1, 2) if isPrime(i) and isPrime(n - i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "composite = bytearray(1000001)\n",
    "for i in range(2, len(composite)):\n",
    "    if not composite[i]:\n",
    "        for j in range(i * 2, len(composite), i):\n",
    "            composite[j] = True\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        return [\n",
    "            [i, n - i]\n",
    "            for i in range(2, n // 2 + 1)\n",
    "            if not composite[i] and not composite[n - i]\n",
    "        ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check_prime(num:int) -> bool:\n",
    "    if num <= 1: return False\n",
    "    i = 2\n",
    "    while i * i <= num:\n",
    "        if num % i == 0:\n",
    "            return False\n",
    "        i += 1\n",
    "    return True\n",
    "\n",
    "prime_list = []\n",
    "for i in range(2, 10 ** 6 + 1):\n",
    "    if check_prime(i):\n",
    "        prime_list.append(i)\n",
    "pl_len = len(prime_list)\n",
    "\n",
    "# 2 3 5 7 11 13\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        left = 0\n",
    "        right = pl_len - 1\n",
    "        while left <= right:\n",
    "            while left < n and prime_list[left] + prime_list[right] < n:\n",
    "                left += 1\n",
    "            while right >= left and prime_list[left] + prime_list[right] > n:\n",
    "                right -= 1\n",
    "            if prime_list[left] + prime_list[right] == n:\n",
    "                if left <= right:\n",
    "                    ans.append([prime_list[left], prime_list[right]])\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from math import sqrt,floor\n",
    "    prime = set()\n",
    "    left = list()\n",
    "    for num in range(2,10**6+1):\n",
    "        sign = True\n",
    "        for i in range(2,floor(sqrt(num))+1):\n",
    "            if num%i==0:\n",
    "                sign = False\n",
    "                break\n",
    "        if sign:\n",
    "            left.append(num)\n",
    "            prime.add(num)\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        for num in Solution.left:\n",
    "            if num>n/2:\n",
    "                break\n",
    "            if n-num in Solution.prime:\n",
    "                res.append([num,n-num])\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def primes_upto(n):\n",
    "    if n<2:\n",
    "        return []\n",
    "    mask=bytearray(b'\\x01'*(n+1))\n",
    "    mask[:2]=[0,0]\n",
    "    for i in range(2, isqrt(n)+1):\n",
    "        mask[i*i::i] = [0]*len(mask[i*i::i])\n",
    "    return [i for i,v in enumerate(mask) if v==1]\n",
    "\n",
    "# print(primes_upto(2))\n",
    "# print(primes_upto(10))\n",
    "# print(primes_upto(100))\n",
    "# print(len(primes_upto(1000)))\n",
    "\n",
    "PS = primes_upto(10**6)\n",
    "PSET = set(PS)\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        for p in PS:\n",
    "            if p*2>n:\n",
    "                break\n",
    "            if n-p in PSET:\n",
    "                ans.append([p, n-p])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isPrime(n):\n",
    "    if n == 2 or n == 3:\n",
    "        return True\n",
    "    if n % 6 not in (1, 5):\n",
    "        return False\n",
    "    for i in range(5, isqrt(n) + 1, 6):\n",
    "        if n % i == 0 or n % (i + 2) == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "all = set()\n",
    "for i in range(2, 10 ** 6):\n",
    "    if isPrime(i):\n",
    "        all.add(i)\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for i in range(2, n + 2 >> 1):\n",
    "            if i in all and n - i in all:\n",
    "                ans.append([i, n - i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isPrime(n):\n",
    "    if n == 2 or n == 3:\n",
    "        return True\n",
    "    if n % 6 not in (1, 5):\n",
    "        return False\n",
    "    for i in range(5, isqrt(n) + 1, 6):\n",
    "        if n % i == 0 or n % (i + 2) == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "all = set()\n",
    "for i in range(2, 10 ** 6):\n",
    "    if isPrime(i):\n",
    "        all.add(i)\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        if n & 1:\n",
    "            if 2 in all and n - 2 in all:\n",
    "                return [[2, n - 2]]\n",
    "        ans = []\n",
    "        for i in range(2, n + 2 >> 1):\n",
    "            if i in all and n - i in all:\n",
    "                ans.append([i, n - i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "p = []\n",
    "for i in range(2, 1000000):\n",
    "    flag = True\n",
    "    for v in p:\n",
    "        if v * v > i: break\n",
    "        if i % v == 0:\n",
    "            flag = False\n",
    "            break\n",
    "    if flag: p.append(i)\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        if n <= 3: return []\n",
    "        ans = []\n",
    "        s = set(p)\n",
    "        for v in p:\n",
    "            if n-v < v: break\n",
    "            if (n-v) in s: ans.append([v, n-v])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "a = []\n",
    "\n",
    "def prime(x):\n",
    "    for i in range(2, int(sqrt(x)) + 1, 1):\n",
    "        if x % i == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "for i in range(2, 10 ** 6 + 1):\n",
    "    if prime(i):\n",
    "        a.append(i)\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        seen = set(a)\n",
    "        res = []\n",
    "        for i in a:\n",
    "            y = n - i\n",
    "            if i <= y and i in seen and y in seen:\n",
    "                res.append([i, y])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    d = {}\n",
    "    maxi = 0\n",
    "\n",
    "    def is_prime(self, num):\n",
    "        if num < self.maxi:\n",
    "            if num in self.d:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        if self.maxi < num:\n",
    "            self.maxi = num\n",
    "\n",
    "        if num == 1:\n",
    "            return False\n",
    "        for i in range(2, int(math.sqrt(num)) + 1):\n",
    "            if num % i == 0:\n",
    "                return False\n",
    "        \n",
    "        self.d[num] = 1\n",
    "        return True\n",
    "\n",
    "    # primes = []\n",
    "    def __init__(self):\n",
    "        if len(self.d) == 0:\n",
    "            for i in range(1, 1000000):\n",
    "                self.is_prime(i)\n",
    "        # print(len(self.d))\n",
    "        # print(self.d)\n",
    "\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        r = []\n",
    "        for i in range(1, n+1):\n",
    "            if i > n-i:\n",
    "                break\n",
    "            if self.is_prime(i) and self.is_prime(n-i):\n",
    "                r.append([i, n-i])\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        f = lambda x: all(x % i for i in range(3, isqrt(x) + 1, 2))\n",
    "        if n & 1 or n <= 4:\n",
    "            return [[2, n - 2]] if n > 3 and f(n - 2) else []\n",
    "        m = n // 2 - 2\n",
    "        a = [True] * m\n",
    "        for i in range(m):\n",
    "            if a[i]:\n",
    "                for j in range(i * i * 2 + 6 * i + 3, m, 2 * i + 3):\n",
    "                    a[j] = False\n",
    "        b = []\n",
    "        for i in range(m // 2):\n",
    "            if a.pop() and a[i]:\n",
    "                t = 2 * i + 3\n",
    "                b.append([t, n - t])\n",
    "        if m & 1 and a.pop():\n",
    "            b.append([2 * len(a) + 3] * 2)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        f = lambda x: all(x % i for i in range(3, isqrt(x) + 1, 2))\n",
    "        if n & 1 or n <= 4:\n",
    "            return [[2, n - 2]] if n > 3 and f(n - 2) else []\n",
    "        m = n // 2 - 2\n",
    "        a, t = [True] * m, 1\n",
    "        for i in range(m):\n",
    "            t += 2\n",
    "            if a[i]:\n",
    "                for j in range(i + t, m, t):\n",
    "                    a[j] = False\n",
    "        b = []\n",
    "        for i in range(m // 2):\n",
    "            if a.pop() and a[i]:\n",
    "                t = 2 * i + 3\n",
    "                b.append([t, n - t])\n",
    "        if m & 1 and a.pop():\n",
    "            b.append([2 * len(a) + 3] * 2)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Prime:\n",
    "    def prime_sieve(self, n):\n",
    "        \"\"\"returns a sieve of primes >= 5 and < n\"\"\"\n",
    "        flag = n % 6 == 2\n",
    "        sieve = bytearray((n // 3 + flag >> 3) + 1)\n",
    "        for i in range(1, int(n ** 0.5) // 3 + 1):\n",
    "            if not (sieve[i >> 3] >> (i & 7)) & 1:\n",
    "                k = (3 * i + 1) | 1\n",
    "                for j in range(k * k // 3, n // 3 + flag, 2 * k):\n",
    "                    sieve[j >> 3] |= 1 << (j & 7)\n",
    "                for j in range(k * (k - 2 * (i & 1) + 4) // 3, n // 3 + flag, 2 * k):\n",
    "                    sieve[j >> 3] |= 1 << (j & 7)\n",
    "        return sieve\n",
    "\n",
    "    def prime_list(self, n):\n",
    "        \"\"\"returns a list of primes <= n\"\"\"\n",
    "        res = []\n",
    "        if n > 1:\n",
    "            res.append(2)\n",
    "        if n > 2:\n",
    "            res.append(3)\n",
    "        if n > 4:\n",
    "            sieve = self.prime_sieve(n + 1)\n",
    "            res.extend(\n",
    "                3 * i + 1 | 1 for i in range(1, (n + 1) // 3 + (n % 6 == 1)) if not (sieve[i >> 3] >> (i & 7)) & 1)\n",
    "        return res\n",
    "\n",
    "    def __init__(self, n) -> None:\n",
    "        self.primes = self.prime_list(n)\n",
    "\n",
    "    def dissolve(self, num):\n",
    "        '''prime factor decomposition of num'''\n",
    "        lst = []\n",
    "        idx = -1\n",
    "        for prime in self.primes:\n",
    "            if prime * prime > num:\n",
    "                break\n",
    "\n",
    "            if num % prime == 0:\n",
    "                lst.append([prime, 0])\n",
    "                idx += 1\n",
    "\n",
    "            while num % prime == 0:\n",
    "                lst[idx][1] += 1\n",
    "                num //= prime\n",
    "\n",
    "        if num != 1:\n",
    "            lst.append([num, 1])\n",
    "\n",
    "        return lst\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ps = Prime(n).primes\n",
    "        buc = set(ps)\n",
    "        res = []\n",
    "        for c in sorted(buc):\n",
    "            if c > (n // 2):\n",
    "                break\n",
    "            if (n - c) in buc and c <= n - c:\n",
    "                res.append([c, n- c])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "a = []\n",
    "\n",
    "def prime(x):\n",
    "    for i in range(2, int(sqrt(x)) + 1, 1):\n",
    "        if x % i == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "for i in range(2, 10 ** 6 + 1):\n",
    "    if prime(i):\n",
    "        a.append(i)\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        seen = set(a)\n",
    "        res = []\n",
    "        for i in range(2, n // 2 + 1):\n",
    "            if i in seen and n - i in seen:\n",
    "                res.append([i, n - i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def eratosthenes(n: int) -> List[int]:\n",
    "    \"\"\"[2, x] 内的质数\"\"\"\n",
    "    primes = []\n",
    "    isPrime = [True] * (n + 1)\n",
    "    for i in range(2, n + 1):\n",
    "        if isPrime[i]:\n",
    "            primes.append(i)\n",
    "            for j in range(i * i, n + 1, i):  # 注意是 *, 不是 +, 比 i 小的 i 的倍数已经被枚举过了\n",
    "                isPrime[j] = False\n",
    "    return primes\n",
    "\n",
    "\n",
    "primes = eratosthenes(10**6)\n",
    "sp = set(primes)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for i in range(len(primes)):\n",
    "            x = primes[i]\n",
    "            if x > n // 2:\n",
    "                break\n",
    "            if n - x in sp:\n",
    "                ans.append([x, n - x])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def sieve_of_eratosthenes(n):\n",
    "    if n < 2:\n",
    "        return []\n",
    "    primes = [True] * (n + 1)  # 初始化为 True，表示所有数都是质数\n",
    "    primes[0], primes[1] = False, False  # 0 和 1 不是质数\n",
    "    # 从 2 开始，依次标记其倍数为合数\n",
    "    for i in range(2, int(n ** 0.5) + 1):\n",
    "        if primes[i]:\n",
    "            for j in range(i * i, n + 1, i):\n",
    "                primes[j] = False\n",
    "    return [i for i in range(2, n + 1) if primes[i]]\n",
    "\n",
    "ps = set(sieve_of_eratosthenes(10 ** 6))\n",
    "sp = sorted(ps)\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        for i in sp:\n",
    "            if i > n // 2: \n",
    "                break\n",
    "            if (n - i) in ps:\n",
    "                res.append([i, n - i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = []\n",
    "def calc(maxN):\n",
    "    vis = [False] * (maxN + 1)\n",
    "    for i in range(2, maxN + 1):\n",
    "        if not vis[i]:\n",
    "            primes.append(i)\n",
    "        for p in primes:\n",
    "            if i * p > maxN:\n",
    "                break\n",
    "            vis[i * p] = True\n",
    "            if i % p == 0:\n",
    "                break\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        if not primes:\n",
    "            calc(10 ** 6)\n",
    "        res = []\n",
    "        left = 0\n",
    "        right = len(primes) - 1\n",
    "        while left <= right:\n",
    "            if primes[left] + primes[right] == n:\n",
    "                res.append([primes[left], primes[right]])\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            elif primes[left] + primes[right] < n:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 6 + 1\n",
    "prime = [1] * N\n",
    "prime[0] = prime[1] = 0\n",
    "for i in range(2,N):\n",
    "    if prime[i]:\n",
    "        for j in range(i * i,N,i):\n",
    "            prime[j] = 0\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for i in range(2,n//2 + 1):\n",
    "            if prime[i]:\n",
    "                if prime[n - i]:\n",
    "                    ans.append([i,n - i])\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "MX = int(1e6 + 1)\n",
    "is_primes = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_primes[i]:\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_primes[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for i in range(2, n // 2 + 1):\n",
    "            if is_primes[i] and is_primes[n-i]: ans.append((i, n-i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 6 - 1\n",
    "is_prime = [True] * N\n",
    "\n",
    "for i in range(2, N):\n",
    "    if is_prime[i]:\n",
    "        for j in range(i*i, N, i):\n",
    "            is_prime[j] = False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        if n < 4:\n",
    "            return []\n",
    "        elif n == 4:\n",
    "            return [[2, 2]]\n",
    "        \n",
    "        if n & 1 == 1:\n",
    "            return [[2, n-2]] if is_prime[n-2] else []\n",
    "        \n",
    "        return [[i, n-i] for i in range(3, n//2 + 1, 2) if is_prime[i] and is_prime[n-i]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 6 + 1\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        left=2\n",
    "        right=n-2\n",
    "        while left<=right:\n",
    "            if is_prime[left] and is_prime[right]:\n",
    "                ans.append([left,right])\n",
    "            if left==2:\n",
    "                left+=1\n",
    "                right-=1\n",
    "            else:\n",
    "                left+=2\n",
    "                right-=2\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "m=10**6+5\n",
    "prime=[True]*m\n",
    "for i in range(2,m):\n",
    "    if prime[i]:\n",
    "        for j in range(i+i,m,i):\n",
    "            prime[j]=False\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        for i in range(2,n+1):\n",
    "            if prime[i] and prime[n-i] and n-i>=i:\n",
    "                ans.append([i,n-i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "a = Counter()\n",
    "\n",
    "def prime(x):\n",
    "    for i in range(2, int(sqrt(x)) + 1, 1):\n",
    "        if x % i == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "for i in range(2, 10 ** 6 + 1):\n",
    "    if prime(i):\n",
    "        a[i] = 1\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        seen = set(a)\n",
    "        res = []\n",
    "        for i in range(2, n // 2 + 1):\n",
    "            if a[i] and a[n - i]:\n",
    "                res.append([i, n - i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class MaxHeap:\n",
    "    def __init__(self, arr: list):\n",
    "        self.heap = [-x for x in arr]\n",
    "        heapq.heapify(self.heap)\n",
    "\n",
    "    def push(self, x):  # 插入元素\n",
    "        heapq.heappush(self.heap, -x)\n",
    "\n",
    "    def pop(self):  # 弹出最大值\n",
    "        return -heapq.heappop(self.heap)\n",
    "\n",
    "    def top(self):  # 返回最大值\n",
    "        return -self.heap[0]\n",
    "\n",
    "\n",
    "class RMinQ:\n",
    "    def __init__(self, arr: list):\n",
    "        self.arr = arr\n",
    "        self.n = len(arr)\n",
    "        self.log = [0] * (self.n + 1)\n",
    "        self.st = [[0] * self.n for _ in range(self.n)]\n",
    "        for i in range(2, self.n + 1):\n",
    "            self.log[i] = self.log[i // 2] + 1\n",
    "        for i in range(self.n):\n",
    "            self.st[i][0] = arr[i]\n",
    "        for j in range(1, self.log[self.n] + 1):\n",
    "            for i in range(self.n - (1 << j) + 1):\n",
    "                self.st[i][j] = min(\n",
    "                    self.st[i][j - 1], self.st[i + (1 << (j - 1))][j - 1]\n",
    "                )\n",
    "\n",
    "    def query(self, l: int, r: int) -> int:\n",
    "        # 闭区间\n",
    "        s = self.log[r - l + 1]\n",
    "        return min(self.st[l][s], self.st[r - (1 << s) + 1][s])\n",
    "\n",
    "\n",
    "def gen_sub_seq(arr: list, proper=False, no_empty=False):\n",
    "    \"\"\"\n",
    "    生成列表 arr 的所有子序列。\n",
    "\n",
    "    参数:\n",
    "    arr (List): 输入的列表。\n",
    "    proper (bool, 可选): 若为 True，则生成真子集（不包括原列表），默认为 False。\n",
    "    no_empty (bool, 可选): 若为 True，则不包括空子集，默认为 False。\n",
    "\n",
    "    返回:\n",
    "    Generator: 一个生成器，用于遍历所有满足条件的子序列。\n",
    "    \"\"\"\n",
    "\n",
    "    n = len(arr)\n",
    "    # 二进制枚举子集\n",
    "    start = 1 if no_empty else 0\n",
    "    end = 1 << n if not proper else (1 << n) - 1\n",
    "    for flag in range(start, end):\n",
    "        res = []\n",
    "        for idx, ele in enumerate(arr):\n",
    "            if 1 << idx & flag:\n",
    "                res.append(ele)\n",
    "\n",
    "        yield res\n",
    "\n",
    "\n",
    "def get_primes(le: int) -> set[int]:\n",
    "    is_prime = [True] * (le + 1)\n",
    "    is_prime[0] = is_prime[1] = False\n",
    "    primes = set()\n",
    "    for x in range(2, le + 1):\n",
    "        if is_prime[x]:\n",
    "            primes.add(x)\n",
    "            # 素数的倍数不是素数\n",
    "            for y in range(x * 2, le + 1, x):\n",
    "                is_prime[y] = False\n",
    "\n",
    "    return primes\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "primes = get_primes(10**6 + 1)\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        \n",
    "        for i in range(1, n // 2 + 1):\n",
    "            if i in primes and n - i in primes:\n",
    "                ans.append([i, n - i])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = OrderedDict()\n",
    "for i in range(2, 1000001):\n",
    "    flag = True\n",
    "    for v in primes:\n",
    "        if i % v == 0:\n",
    "            flag = False\n",
    "            break\n",
    "        if v * v > i:\n",
    "            break\n",
    "    if flag:\n",
    "        primes[i] = True\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        for i in primes:\n",
    "            sub = n - i\n",
    "            if sub < i:\n",
    "                break\n",
    "            if sub in primes:\n",
    "                res.append([i, sub])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "max=1000_000\n",
    "isprime = [True] * (max + 1)\n",
    "primes = []\n",
    "for i in range(2, max//2+1):\n",
    "    if isprime[i]:\n",
    "        primes.append(i)\n",
    "    for j in primes:\n",
    "        if i * j >= (max + 1):\n",
    "            break\n",
    "        isprime[i * j] = False\n",
    "        if i % j == 0:\n",
    "            break\n",
    "        \n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ret=[]\n",
    "        if n == 1 or  n == 3:\n",
    "            return []\n",
    "        if n == 4:\n",
    "            return [[2,2]]\n",
    "        if n % 2 == 0 :\n",
    "            for x in range(3,n//2+1,2):\n",
    "                if isprime[x] and isprime[n-x]:\n",
    "                    ret.append([x,(n-x)])\n",
    "            return ret\n",
    "        else:\n",
    "            return [[2,n-2]] if isprime[n-2] else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000000\n",
    "isPrime = [1] * N\n",
    "arr = []\n",
    "for i in range(2, N):\n",
    "    if isPrime[i]:\n",
    "        arr.append(i)\n",
    "        for j in range(i * i, N, i):\n",
    "            isPrime[j] = 0\n",
    "m = len(arr)\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        i, j = 0, m-1\n",
    "        while i <= j:\n",
    "            s = arr[i] + arr[j]\n",
    "            if s == n:\n",
    "                ans.append([arr[i], arr[j]])\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            elif s > n:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n):\n",
    "        def sieve_of_eratosthenes(n):\n",
    "            is_prime = [True] * (n+1)\n",
    "            is_prime[0], is_prime[1] = False, False\n",
    "            for i in range(2, int(n**0.5)+1,1):\n",
    "                if is_prime[i] == True:\n",
    "                    for j in range(i * i, n + 1, i):\n",
    "                        is_prime[j] = False\n",
    "            primes = [num for num, prime in enumerate(is_prime) if prime]\n",
    "            return primes\n",
    "        prime_numbers = sieve_of_eratosthenes(n)\n",
    "        res = []\n",
    "\n",
    "        left, right = 0, len(prime_numbers)-1\n",
    "        while left <= right:\n",
    "            # print(left, right, prime_numbers[left], prime_numbers[right])\n",
    "            if prime_numbers[left] + prime_numbers[right] == n:\n",
    "                res.append([prime_numbers[left], prime_numbers[right]])\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            elif prime_numbers[left] + prime_numbers[right] < n:\n",
    "                left += 1\n",
    "            elif prime_numbers[left] + prime_numbers[right] > n:\n",
    "                right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 6 + 10\n",
    "primes = []\n",
    "vis = [False] * N \n",
    "\n",
    "for i in range(2, N):\n",
    "    if not vis[i]:\n",
    "        primes.append(i)\n",
    "    \n",
    "    j = 0\n",
    "    while primes[j] <= (N-1) // i:\n",
    "        vis[i * primes[j]] = True\n",
    "        if i % primes[j] == 0: break\n",
    "        j += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        if n % 2: return [(2, n-2)] if n > 4 and not vis[n-2] else []\n",
    "        ans = []\n",
    "        \n",
    "        for x in primes:\n",
    "            y = n-x \n",
    "            if y < x: break \n",
    "            if not vis[y]: ans.append((x, y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "prime = []\n",
    "is_prime = [True] * 1000007\n",
    "\n",
    "for i in range(2, 1000007):\n",
    "    if not is_prime[i]: continue\n",
    "    prime.append(i)\n",
    "    for j in range(i * 2, 1000007, i):\n",
    "        is_prime[j] = False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        i = 0\n",
    "        ans = []\n",
    "        while prime[i] <= n // 2:\n",
    "            if is_prime[n - prime[i]]:\n",
    "                ans.append([prime[i], n - prime[i]])\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 6 + 1\n",
    "primes = []\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        if n % 2:\n",
    "            return [[2, n - 2]] if n > 4 and is_prime[n - 2] else []\n",
    "        ans = []\n",
    "        for x in primes:\n",
    "            y = n - x\n",
    "            if y < x:\n",
    "                break\n",
    "            if is_prime[y]:\n",
    "                ans.append([x, y])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "MX = 10**6 + 1\r\n",
    "primes = []\r\n",
    "is_primes = [True] * MX\r\n",
    "\r\n",
    "for p in range(2, MX):\r\n",
    "    if is_primes[p]:\r\n",
    "        primes.append(p)\r\n",
    "        for q in range(p * p, MX, p):\r\n",
    "            is_primes[q] = False\r\n",
    "\r\n",
    "class Solution:\r\n",
    "       \r\n",
    "\r\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\r\n",
    "\r\n",
    "        if n % 2:\r\n",
    "            return [[2, n-2]] if n > 4 and is_primes[n-2] else []\r\n",
    "        ans  = []\r\n",
    "        for x in primes:\r\n",
    "            y = n - x\r\n",
    "            if y < x:\r\n",
    "                break\r\n",
    "            if is_primes[y]:\r\n",
    "                ans.append([x, y])\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 6 + 1\n",
    "primes = []\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        if n % 2:\n",
    "            return [[2, n - 2]] if n > 4 and is_prime[n - 2] else []\n",
    "        ans = []\n",
    "        for x in primes:\n",
    "            y = n - x\n",
    "            if y < x:\n",
    "                break\n",
    "            if is_prime[y]:\n",
    "                ans.append([x, y])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        isprime = [True] * (n + 1)\n",
    "        prime = []\n",
    "        for i in range(2, n + 1):\n",
    "            if isprime[i]:\n",
    "                prime.append(i)\n",
    "            for p in prime:\n",
    "                if i * p > n:\n",
    "                    break\n",
    "                isprime[i * p] = False\n",
    "                if i % p == 0:\n",
    "                    break\n",
    "        ans = []\n",
    "        for i in range(2, n // 2 + 1):\n",
    "            if isprime[i] and isprime[n - i]:\n",
    "                ans.append([i, n - i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "# 筛选出1-N中的质数\n",
    "def get_prime(N):\n",
    "    prime_vals = []\n",
    "    flag = [True] * (N+1)\n",
    "    flag[1] = False\n",
    "\n",
    "    for val in range(2, N+1):\n",
    "        if flag[val]:\n",
    "            prime_vals.append(val)\n",
    "\n",
    "        for p_val in prime_vals:\n",
    "            if val * p_val > N:\n",
    "                break\n",
    "\n",
    "            flag[val * p_val] = False\n",
    "\n",
    "            if val % p_val == 0:\n",
    "                break\n",
    "\n",
    "    return prime_vals\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        if n == 1:\n",
    "            return []\n",
    "\n",
    "        p = get_prime(n)\n",
    "        ss = set(p)\n",
    "\n",
    "        ret = []\n",
    "        for v in ss:\n",
    "            if n-v in ss and n-v >= v:\n",
    "                ret.append([v, n-v])\n",
    "\n",
    "        ret.sort()\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 6 + 1\n",
    "primes = []\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        tmp = n//2\n",
    "        res = []\n",
    "        if tmp < 2:\n",
    "            return []\n",
    "        else:\n",
    "            if n % 2 != 0:\n",
    "                if is_prime[n-2]:\n",
    "                    res.append([2, n-2])\n",
    "                    return res\n",
    "                else:\n",
    "                    return []\n",
    "            for j in range(2, tmp+1):\n",
    "                if is_prime[j] and is_prime[n-j]:\n",
    "                    res.append([j, n-j])\n",
    "            return res            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000001\n",
    "isPrime = [False, False] + [True] * N\n",
    "for i in range(N):\n",
    "    if not isPrime[i]: continue\n",
    "    for j in range(i * i, N, i):\n",
    "        isPrime[j] = False\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for x in range(1, n // 2 + 1):\n",
    "            if isPrime[x] and isPrime[n - x]:\n",
    "                ans.append([x, n-x])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 6 + 1\n",
    "primes = []\n",
    "is_prime = [True] * MX\n",
    "\n",
    "for i in range(2, MX): \n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "    for j in range(i * 2, MX, i):\n",
    "        is_prime[j] = False\n",
    "\n",
    "primes = set(primes)\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        ans = set()\n",
    "        for p in primes:\n",
    "            if p <= n:\n",
    "                if n - p in primes:\n",
    "                    cur = [p, n - p]\n",
    "                    cur.sort()\n",
    "                    ans.add(tuple(cur))\n",
    "        ans = list(ans)\n",
    "        ans.sort()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mx = 10**6 + 1\n",
    "# mx = 100\n",
    "is_prime = [True] * mx \n",
    "primes = set()\n",
    "for i in range(2, mx):\n",
    "    if is_prime[i]:\n",
    "        primes.add(i)\n",
    "        for j in range(i*i, mx, i):\n",
    "            is_prime[j] = False \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans = set()\n",
    "        for x in primes:\n",
    "            if n - x in primes and x <= n // 2:\n",
    "                ans.add((x, n - x))\n",
    "        ans = list(ans)\n",
    "        ans.sort(key=lambda x: x[0])\n",
    "        return ans\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def tag_primes_eratosthenes(n):  \n",
    "    # 埃氏筛,筛出[0,n)区间内的所有质数   \n",
    "    # 第1e5个数字是1299709\n",
    "    primes = [ True ]*n\n",
    "    primes[ 0 ] = primes[ 1 ] = False  # 0和1不是质数\n",
    "    for i in range(2,int(n**0.5)+1):\n",
    "        if primes[i]:\n",
    "            primes[i * i::i] = [ False ] * ((n - 1 - i * i) // i + 1)\n",
    "    return primes\n",
    "\n",
    "p=tag_primes_eratosthenes(10**6+5)\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        res=[]\n",
    "        for i in range(1,n+1):\n",
    "            j=n-i\n",
    "            if j<i:\n",
    "                break\n",
    "            if p[i] and p[j]:\n",
    "                res.append([i,j])\n",
    "        return res\n",
    "            \n",
    "        \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 6\n",
    "flag_list = [False] * (N + 1)\n",
    "flag_list[0] = flag_list[1] = True\n",
    "for i in range(2, int((N+0.5)**0.5) + 1):\n",
    "    if flag_list[i]:\n",
    "        continue\n",
    "    for j in range(i, N // i + 1):\n",
    "        flag_list[i * j] = True\n",
    "prime_list = [i for i, v in enumerate(flag_list) if not v]\n",
    "prime_set = set(prime_list)\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ret = []\n",
    "        half_n = n//2\n",
    "        for p in prime_list:\n",
    "            if p > half_n:\n",
    "                break\n",
    "            p2 = n - p\n",
    "            if p2 in prime_set:\n",
    "                ret.append([p, p2])\n",
    "        return ret            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mx=10**6+1\n",
    "primes=[]\n",
    "is_prime=[1]*mx\n",
    "for i in range(2,mx):\n",
    "  if is_prime[i]:\n",
    "    primes.append(i)\n",
    "    for j in range(i,mx,i):\n",
    "      is_prime[j]=0\n",
    "primes_=set(primes)\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "      result=[]\n",
    "      for x in primes:\n",
    "        if x>n-x:\n",
    "          break\n",
    "        if (n-x) in primes_:\n",
    "          result.append([x,n-x])\n",
    "      return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.n = n\n",
    "        self.primes = primes = []  # 所有n以内的质数\n",
    "        self.min_div = min_div = [0] * (n + 1)  # md[i]代表i的最小(质)因子\n",
    "        min_div[1] = 1\n",
    "\n",
    "        # 欧拉筛O(n)，顺便求出min_div\n",
    "        for i in range(2, n + 1):\n",
    "            if not min_div[i]:\n",
    "                primes.append(i)\n",
    "                min_div[i] = i\n",
    "            for p in primes:\n",
    "                if i * p > n: break\n",
    "                min_div[i * p] = p\n",
    "                if i % p == 0:\n",
    "                    break\n",
    "\n",
    "    def getPrimes(self)->List:\n",
    "        return self.primes\n",
    "    def isPrime(self, x: int):\n",
    "        \"\"\"检测是否是质数，最坏是O(sqrt(x)\"\"\"\n",
    "        if x < 3: return x == 2\n",
    "        if x <= self.n: return self.min_div[x] == x\n",
    "        for i in range(2, int(x ** 0.5) + 1):\n",
    "            if x % i == 0: return False\n",
    "        return True\n",
    "\n",
    "    def factorization(self, x: int):\n",
    "        \"\"\"分解质因数，\n",
    "        返回一个迭代器，每个迭代器为(p1,v1)，满足p1**v1 * p2**v2 * ... * pn**vn == x\n",
    "        如果x是质数，会返回为单个迭代器,为(x,1)\n",
    "        复杂度\n",
    "        1. 若x>n则需要从2模拟到sqrt(x)，如果中间x降到n以下则走2；最坏情况，不含低于n的因数，则需要开方复杂度\n",
    "        2. 否则x质因数的个数，那么最多就是O(lgx)\"\"\"\n",
    "        n, min_div = self.n, self.min_div\n",
    "        for p in range(2, int(x ** 0.5) + 1):\n",
    "            if x <= n: break\n",
    "            if x % p == 0:\n",
    "                cnt = 0\n",
    "                while x % p == 0: cnt += 1; x //= p\n",
    "                yield p, cnt\n",
    "        while 1 < x <= n:\n",
    "            p, cnt = min_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= n and x > 1:\n",
    "            yield x, 1\n",
    "    def getFactors(self, x: int)->List:\n",
    "        \"\"\"求x的所有因数，包括1和x\"\"\"\n",
    "        factors = [1]\n",
    "        for p, b in self.factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b + 1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "        return factors\n",
    "\n",
    "    def mr_is_prime(self, x):\n",
    "        \"\"\"\n",
    "        Miller-Rabin 检测. 检测x是否是质数，置信度: 1 - (1/4)^k. 复杂度k*log^3\n",
    "        但是longlong以内可以用k==3或7的代价，换取100%置信度\n",
    "        https://zhuanlan.zhihu.com/p/349360074\n",
    "        \"\"\"\n",
    "        if x < 3 or x % 2 == 0:\n",
    "            return x == 2\n",
    "        if x % 3 == 0:\n",
    "            return x == 3\n",
    "\n",
    "        u, t = x - 1, 0\n",
    "        while not u & 1:\n",
    "            u >>= 1\n",
    "            t += 1\n",
    "        ud = (2, 325, 9375, 28178, 450775, 9780504, 1795265022)  # long long 返回用这个7个数检测100%正确\n",
    "        # ud = (2, 7, 61)  # int 返回用这3个数检测100%正确\n",
    "        # for _ in range(k):\n",
    "        #     a = random.randint(2, x - 2)\n",
    "        for a in ud:\n",
    "            v = pow(a, u, x)\n",
    "            if v == 1 or v == x - 1 or v == 0:\n",
    "                continue\n",
    "            for j in range(1, t + 1):\n",
    "                v = v * v % x\n",
    "                if v == x - 1 and j != t:\n",
    "                    v = 1\n",
    "                    break\n",
    "                if v == 1:\n",
    "                    return False\n",
    "            if v != 1:\n",
    "                return False\n",
    "        return True\n",
    "st = PrimeTable(10**6)\n",
    "primes = st.getPrimes()\n",
    "primes_set = {e for e in primes}\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for i in range(len(primes)):\n",
    "            if primes[i]>=n//2+3:\n",
    "                break\n",
    "            if n-primes[i] in primes_set and primes[i]<=n-primes[i]:\n",
    "                ans.append([primes[i],n-primes[i]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "total = 10 ** 6\n",
    "primes = set()\n",
    "flag = [False] * total\n",
    "for i in range(2, total):\n",
    "    if not flag[i]:\n",
    "        primes.add(i)\n",
    "        for j in range(i * i, total, i):\n",
    "            flag[j] = True\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        for i in range(2, n // 2 + 1):\n",
    "            if i in primes and n - i in primes:\n",
    "                res.append([i, n - i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# 使用列表记录10^6的质数；\n",
    "mx=10**6+1\n",
    "isprime=[True]*mx\n",
    "prime=set()\n",
    "for i in range(2,mx):\n",
    "    if isprime[i]:\n",
    "        prime.add(i)\n",
    "        for j in range(i*i,mx,i):\n",
    "            isprime[j]=False\n",
    "# print(prime)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        # 判断i和n-i是否在在列表中\n",
    "        ans=[]\n",
    "        for i in range(n//2+1):\n",
    "            if i in prime and (n-i) in prime:\n",
    "                ans .append([i,n-i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        sushu=[1]*(n+1)\n",
    "        for i in range(2 ,n+1):\n",
    "            if sushu[i]:\n",
    "                for j in range(2*i,n+1,i):\n",
    "                    sushu[j]=0\n",
    "        ans=[]\n",
    "        for i in range(2,n//2+1):\n",
    "            if sushu[i] and sushu[n-i]:\n",
    "                ans.append([i,n-i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        isP = [1] * (n + 1)\n",
    "        isP[1] = 0\n",
    "        isP[0] = 0\n",
    "        ans = list()\n",
    "        for i in range(2, n):\n",
    "            if isP[i]:\n",
    "                for j in range(i, n // i + 1):\n",
    "                    isP[i * j] = 0\n",
    "        for i in range(2, n // 2 + 1):\n",
    "            if isP[i] and isP[n - i]:\n",
    "                ans.append([i, n - i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        if n <= 1:\n",
    "            return []\n",
    "        prime = [True]*n\n",
    "        prime[1] = False\n",
    "        for i in range(2,floor(math.sqrt(n))+1):\n",
    "            if prime[i]:\n",
    "                for j in range(2*i,n,i):\n",
    "                    prime[j] = False\n",
    "        ans = []\n",
    "        for i in range(1, n//2+1):\n",
    "            if prime[i] and prime[n-i]:\n",
    "                ans.append([i, n-i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        if n < 4: return []\n",
    "        res = []\n",
    "        isPrime = [1] * n\n",
    "        isPrime[0] = isPrime[1] = 0\n",
    "        cnt = 0\n",
    "        for i in range(2, n):\n",
    "            if isPrime[i]:\n",
    "                for j in range(i * i, n, i):\n",
    "                    isPrime[j] = 0\n",
    "                if i >= n / 2 and isPrime[n - i]:\n",
    "                    res.append([n - i, i])\n",
    "        res.reverse()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 6 + 10\n",
    "primes = []\n",
    "vis = [False] * N \n",
    "\n",
    "for i in range(2, N):\n",
    "    if not vis[i]:\n",
    "        primes.append(i)\n",
    "    \n",
    "    j = 0\n",
    "    while primes[j] <= (N-1) // i:\n",
    "        vis[i * primes[j]] = True\n",
    "        if i % primes[j] == 0: break\n",
    "        j += 1\n",
    "\n",
    "d = Counter(primes)\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        \n",
    "        for i in range(n-1, (n+1)//2 - 1, -1):\n",
    "            if i in d and (n-i) in d:\n",
    "                ans.append([n-i, i])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxn = 10 ** 6\n",
    "prime = [0 for _ in range(10 ** 6 + 1)]\n",
    "for i in range(2, maxn + 1):\n",
    "    if prime[i] == 0:\n",
    "        prime[0] += 1\n",
    "        prime[prime[0]] = i\n",
    "    for j in range(1, prime[0] + 1):\n",
    "        if prime[j] > maxn // i: break\n",
    "        prime[prime[j] * i] = 1\n",
    "        if i % prime[j] == 0: break\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        # maxn = n\n",
    "        # prime = [0 for _ in range(maxn + 1)]\n",
    "        # def getPrime():\n",
    "        #     for i in range(2, maxn + 1):\n",
    "        #         if prime[i] == 0:\n",
    "        #             prime[0] += 1\n",
    "        #             prime[prime[0]] = i\n",
    "        #         for j in range(1, prime[0] + 1):\n",
    "        #             if prime[j] > maxn // i: break\n",
    "        #             prime[prime[j] * i] = 1\n",
    "        #             if i % prime[j] == 0: break\n",
    "        # getPrime()\n",
    "        ans = []\n",
    "        vis = {}\n",
    "        for i in range(1, prime[0] + 1):\n",
    "            vis[prime[i]] = 1\n",
    "        # print(prime[0])\n",
    "        for i in range(1, prime[0] + 1):\n",
    "            if prime[i] >= n: break\n",
    "            if n - prime[i] in vis and prime[i] <= n - prime[i]:\n",
    "                ans.append([prime[i], n - prime[i]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        # def isPrime(num):\n",
    "        #     if num == 2:\n",
    "        #         return True\n",
    "        #     if num < 2 or num % 2 == 0:\n",
    "        #         return False\n",
    "        #     for i in range(3, int(sqrt(num))+1, 2):\n",
    "        #         if num % i == 0:\n",
    "        #             return False\n",
    "        #     return True\n",
    "        if n <= 3:\n",
    "            return []\n",
    "        res = []\n",
    "        record = [True] * (n+1)\n",
    "        for i in range(2, int(sqrt(n))+1):\n",
    "            for j in range(2*i, n+1, i):\n",
    "                record[j] = False\n",
    "        # record[2] = True\n",
    "        if record[n-2]:\n",
    "                res.append([2, n-2])\n",
    "        # print(record)\n",
    "        # flag = -1\n",
    "        for i in range(3, n//2+1, 2):\n",
    "            if record[i] and record[n-i]:\n",
    "                res.append([i, n-i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        is_primes = [True] * (n+1)\n",
    "        primes = set()\n",
    "        for i in range(2, n+1):\n",
    "            if is_primes[i]:\n",
    "                primes.add(i)\n",
    "                for j in range(i*i, n+1, i):\n",
    "                    is_primes[j] = False\n",
    "        result = []\n",
    "        for num in sorted(primes):\n",
    "            if n-num in primes and n-num >= num:\n",
    "                result.append([num, n-num])\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        def ePrime(n):\n",
    "            primes = [False] * 2 + [True] * (n - 1)\n",
    "            for i in range(2, n + 1):\n",
    "                if primes[i]:\n",
    "                    for j in range(i * i, n + 1, i):\n",
    "                        primes[j] = False\n",
    "            return primes\n",
    "        \n",
    "        primes = ePrime(n)\n",
    "        res = []\n",
    "        for i in range(2, n // 2 + 1):\n",
    "            if primes[i] and primes[n - i]:\n",
    "                res.append([i, n - i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 6 + 1\n",
    "prime = [1] * N\n",
    "prime[0] = prime[1] = 0\n",
    "for i in range(2,N):\n",
    "    if prime[i]:\n",
    "        for j in range(i * i,N,i):\n",
    "            prime[j] = 0\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        cnt = Counter()\n",
    "        for i in range(2,n + 1):\n",
    "            if not prime[i]:\n",
    "                continue\n",
    "            else:\n",
    "                cnt[i] += 1\n",
    "                if cnt[n - i]:\n",
    "                    ans.append([n - i,i])\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    " \n",
    "# test_sl = SortedList([3,5,1,2,7,6,4])\n",
    " \n",
    "# print(test_sl)\n",
    "\n",
    "# test_sl.add(2) #添加元素\n",
    "\n",
    "# test_sl.remove(4) #删除元素 元素不存在时会报错\n",
    "# test_sl.discard(1) #删除元素 元素不存在时不会报错\n",
    "\n",
    "# test_sl.pop() #移除最后一个元素\n",
    "\n",
    "# pos_left = test_sl.bisect_left(2) #查找元素存在的位置\n",
    "# pos_right = test_sl.bisect_right(2)\n",
    "# print(pos_left, pos_right) \n",
    " \n",
    "# num = test_sl.count(2) #计数\n",
    "# print(num)\n",
    " \n",
    "# ind = test_sl.index(2) #返回第一次出现的下标\n",
    "# print(ind)\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        is_prime = [True for i in range(n + 1)]\n",
    "        is_prime[0] = is_prime[1] = False\n",
    "        i = 2\n",
    "        while i <= n:\n",
    "            if is_prime[i]:\n",
    "                j = i\n",
    "                while i * j <= n:\n",
    "                    is_prime[i*j] = False\n",
    "                    j += 1\n",
    "            i += 1 + i % 2\n",
    "        if n % 2 == 1:\n",
    "            if is_prime[n - 2]:\n",
    "                return [[2, n - 2]]\n",
    "            else:\n",
    "                return []\n",
    "        primes = []\n",
    "        for i in range(n + 1):\n",
    "            if is_prime[i]:\n",
    "                primes.append(i)\n",
    "        # print(primes)\n",
    "        res = []\n",
    "        i = 0\n",
    "        while i < len(primes):\n",
    "            val = primes[i]\n",
    "            i += 1\n",
    "        # for val in primes:\n",
    "            if n - val < val:\n",
    "                break\n",
    "            if is_prime[val] and is_prime[n - val]:\n",
    "                res.append([val, n - val])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        isprime=[1]*(n+1)\n",
    "        map1=defaultdict(int)\n",
    "        res=[]\n",
    "        for i in range(2,n+1):\n",
    "            if isprime[i]==1:\n",
    "                for j in range(2,(n//i)+1):\n",
    "                    isprime[i*j]=0\n",
    "                map1[i]=1\n",
    "        for k in map1.keys():\n",
    "            if k>n//2:\n",
    "                break\n",
    "            if map1.get(n-k,0)!=0:\n",
    "                res.append([k,n-k])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        \n",
    "        res=set()\n",
    "        v=[0]*(n+1)\n",
    "        ans=[]\n",
    "        for i in range(2,n+1):\n",
    "            if not v[i]:\n",
    "                if n-i in res:\n",
    "                    if n-i<i:\n",
    "                        ans.append([n-i,i]) \n",
    "                if n==2*i: ans.append([n-i,i]) \n",
    "                res.add(i)\n",
    "                for j in range(i,n//i+1):\n",
    "                    v[i*j]=1\n",
    "        #print(res)\n",
    "        return sorted(ans) \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        is_prime = [True] * (n + 1)\n",
    "        is_prime[0] = is_prime[1] = False\n",
    "        prime_numbers = []\n",
    "        \n",
    "        for i in range(2, int(n ** 0.5) + 1):\n",
    "            if is_prime[i]:\n",
    "                for j in range(i * i, n + 1, i):\n",
    "                    is_prime[j] = False\n",
    "        \n",
    "        for i in range(2, n + 1):\n",
    "            if is_prime[i]:\n",
    "                prime_numbers.append(i)\n",
    "                \n",
    "        i, j = 0, len(prime_numbers) - 1\n",
    "\n",
    "        res = []\n",
    "        if j < 1:\n",
    "            return res\n",
    "        while i <= j:\n",
    "            s = prime_numbers[i] + prime_numbers[j]\n",
    "            if s == n:\n",
    "                res.append([prime_numbers[i], prime_numbers[j]])\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            elif s < n:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "             \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 6 + 1\n",
    "\n",
    "primes = []\n",
    "\n",
    "is_prime = [True] * MX\n",
    "\n",
    "for i in range(2, MX):\n",
    "\n",
    "    if is_prime[i]:\n",
    "\n",
    "        primes.append(i)\n",
    "\n",
    "        for j in range(i * i, MX, i):\n",
    "\n",
    "            is_prime[j] = False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPrimePairs(self, n: int) -> List[List[int]]:\n",
    "        hashmap = set()\n",
    "        ans = []\n",
    "        if n<=2:\n",
    "            return []\n",
    "        for i in range(2,n):\n",
    "            if is_prime[i]:\n",
    "                hashmap.add(i)\n",
    "                if n-i in hashmap:\n",
    "                    ans.append([n-i,i])\n",
    "        ans.reverse()\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
